package developer.算法.栈.柱形图中的最大矩形;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author zhangyongkang
 * @time 2025/4/3 15:35
 * @description 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * <p>
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入： heights = [2,4]
 * 输出： 4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */
public class MaxT {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(solution.largestRectangleArea(new int[]{2, 4}));
    }


    static class Solution3 {
        //维护两个单调栈 一个是从当前往左数 第一个比他小的索引
        //一个往右数  第一个比他小的索引 随后做计算即可
    }

    //单调栈
    static class Solution {
        public int largestRectangleArea(int[] heights) {
            /*
            单调栈的思路
            记录当前节点的左侧和右侧 大于等于该节点的最外侧索引
             */
            int length = heights.length;

            int[] left = new int[length];
            int[] right = new int[length];
            //先记录左侧
            Stack<Integer> leftStack = new Stack<>();
            for (int i = 0; i < heights.length; i++) {
                int currentVal = heights[i];
                //如果当前值大于历史数据
                while (!leftStack.isEmpty() && currentVal <= heights[leftStack.peek()]) {//
                    //比当前值大的都移除
                    leftStack.pop();
                }
                //如果比当前值大的为空
                //这里注意边界处理 取的是当前节点的最左侧&&最右侧 但是不包含边界条件的节点
                left[i] = leftStack.isEmpty() ? -1 : leftStack.peek();
                leftStack.push(i);
            }

            Stack<Integer> rightStack = new Stack<>();
            for (int i = heights.length - 1; i >= 0; i--) {
                int currentVal = heights[i];
                while (!rightStack.isEmpty() && currentVal <= heights[rightStack.peek()]) {
                    rightStack.pop();
                }
                right[i] = rightStack.isEmpty() ? length : rightStack.peek();
                rightStack.push(i);
            }
            int ans = 0;
            for (int i = 0; i < length; i++) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }

            return ans;
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/266844/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    static class SolutionOfficial {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[n];
            int[] right = new int[n];

            Deque<Integer> mono_stack = new ArrayDeque<Integer>();
            for (int i = 0; i < n; ++i) {
                while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                    mono_stack.pop();
                }
                left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
                mono_stack.push(i);
            }

            mono_stack.clear();
            for (int i = n - 1; i >= 0; --i) {
                while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                    mono_stack.pop();
                }
                right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
                mono_stack.push(i);
            }

            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    }


}
